package com.south.base.test;

import org.junit.Assert;
import org.junit.Test;

/**
 * 质数
 * @author Administrator
 * @date 2020/6/18 15:38
 */
public class Primes {
    /**
     * 计数质数
     */
    @Test
    public void countPrimes() {
        Assert.assertEquals(4, countPrimes(10));
    }
    public int countPrimes(int n) {
        if (n <= 2) {
            return 0;
        }
        // 首先去掉一半的偶数
        int count = n / 2;
        boolean[] isPrimes = new boolean[n];
        for (int i = 3; i * i < n; i += 2) {
            // 不是质数 => continue
            if (isPrimes[i]) {
                continue;
            }
            for (int j = i * i; j < n; j += 2 * i) {
                if (!isPrimes[j]) {
                    count--;
                    isPrimes[j] = true;
                }
            }
        }
        return count;
    }
}
